package com.ww.springboot.boot.algorithm.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.stream.Collectors;

/**
 * 描述：
 * 给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
 * <p>
 * 解题思路:顺序入栈 如果当前值比栈顶小
 *
 * @author wanwei
 * @since 2021-06-15 21:09
 */
public class RemoveDuplicateLetters {
    public static void main(String[] args) {
        String s = "abacb";
        System.out.println(method(s));
    }

    private static String method(String s) {
        Stack<Character> stackSelf = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            Character ch = s.charAt(i);
            if (!stackSelf.contains(ch)) {
                while (!stackSelf.isEmpty() && stackSelf.peek() > ch && s.indexOf(stackSelf.peek(), i) != -1) {
                    stackSelf.pop();
                }
                stackSelf.push(ch);
            }
        }

        char chars[] = new char[stackSelf.size()];
        for (int i = 0; i < stackSelf.size(); i++) {
            chars[i] = stackSelf.get(i);
        }
        return new String(chars);
    }
}